package Simple;


import java.util.Arrays;  
import java.util.Comparator;  
import java.util.Set;  
import java.util.TreeSet;

/** 
 * POJ 1177 (线段树+离散化+扫描线)，题目链接为http://poj.org/problem?id=1177 
 *  
 *  
 * 关于扫描线（ScanLine）和线段树结点（Node）各字段的定义，请参看陈宏的论文： 
 * 《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》链接为
 * http://wenku.baidu.com/view/1856cf84b9d528ea81c77918.html 
 * 强烈建议将上面的论文看一遍，因为各字段的定义和计算不好理解 
 *  
 * 个人理解： 
 * 离散化： 
 * 例如有如下三条线段：(-100,-90)(10,20)(3333,4444) 
 * 如果建立的线段树是Tree(-100, 4444)那会浪费相当多的空间 
 * 所谓离散化就是把这三条线段映射成：(0,1)(2,3)(4,5)建立的线段树为Tree(0,5) 
 * 插入和删除时要注意把真实值映射成离散值再操作树 
 * 本题在解题时还要注意把数组y的值去重 
 *  
 * 轮廓周长计算方法： 
 * 有两种 
 * 1.先扫描竖边，再扫描横边，两者相加 
 * 2.只扫描竖边，一边扫描一边加上横边。扫描时前后两条扫描边在x轴的距离则为横边的长度 
 * 下面的代码是按第2种方法来执行的 
 *  
 * 采用上面的第2种方法时，横边的计算上面讲了，那竖边怎么办呢？ 
 * 因为前后两条扫描线是有可能有重叠的，因此周长的增量只是这两条线在y轴上的长度差（|Tree1.M - Tree2.M|） 
 *  
 * 1.下面的代码用数组来保存线段树 
 * 用链表会更用更少的空间，有空再写一个 
 * 2.下面的线段树的叶子结点为[i,i+1]，而不是[i,i] 
 *  
 * 
 */  
public class SegmentTreePOJ1177 {
	//扫描线（竖线）  
    class ScanLine {  
        int x;  //x坐标  
        int y1; //顶点的y坐标  
        int y2; //底端点的y坐标  
        int flag;   //1=入边，0=出边。从左到右扫描时，矩形的左边称为入边，右边称为出边  
    }  
  
    //线段树的结点，也就是一条线段  
    class Node {  
        int left;   //线段的左值  
        int right;  //线段的右值  
        int count;  //线段出现的次数  
        int line;   //线段跨越了几个段。如对于Node[1,5]，三个子结点[1,2]，[2,3]，[4,5]线段被覆盖，则line=2，因为 [1,2]，[2,3]是连续的  
        int lbd;    //左值是否出现（覆盖）过  
        int rbd;    //右值是否出现（覆盖）过  
        int m;      //以本结点为根结点的子树代表的长度  
    }  
      
    Node[] node;  
    ScanLine[] scan;  
    int[] y;  
      
    public static void main(String[] args) {  
        //左下方和右上方的两个点(x1,y1)(x2,y2)定义了一个矩形。共7个矩形，14个点  
        int[][] input = {  
                { -15, 0, 5, 10, },   
                { -5, 8, 20, 25, },  
                { 15, -4, 24, 14, },   
                { 0, -6, 16, 4, },   
                { 2, 15, 10, 22, },  
                { 30, 10, 36, 20, },   
                { 34, 0, 40, 16, },  
        };  
        new SegmentTreePOJ1177().process(input);  
    }  
  
  
    public void process(int[][] input) {  
        init(input.length);  
          
        //读入并保存扫描线  
        int i = 0;  
        for (int[] segment : input) {  
            scan[i].x = segment[0];  
            scan[i].y1 = segment[1];  
            scan[i].y2 = segment[3];  
            scan[i].flag = 1;  
            y[i] = segment[1];  
            i++;  
            scan[i].x = segment[2];  
            scan[i].y1 = segment[1];  
            scan[i].y2 = segment[3];  
            scan[i].flag = 0;  
            y[i] = segment[3];  
            i++;  
        }  
          
        //将扫描线按x坐标的大小从左到右排序；x坐标相等的，入边在前，出边在后  
        Arrays.sort(scan, new Comparator<ScanLine>() {  
            public int compare(ScanLine line1, ScanLine line2) {  
                if (line1.x == line2.x) {  
                    return line1.flag - line2.flag;  
                }  
                return line1.x - line2.x;  
            }  
        });  
          
        //得到离散化后的值再建线段树  
        Set<Integer> set = sortAndMakeUnique(y);  
        int N = set.size();  
        y = new int[N];  
        int j = 0;  
        for(Integer ele : set) {  
            y[j++] = ele;  
        }  
        build(0, N - 1, 0);  
          
        int perimeter = 0;  
        int now_m = 0;  
        int now_line = 0;  
        for(int k = 0, len = scan.length; k < len; k++) {  
            if (scan[k].flag == 1) {  
                insert(scan[k].y1, scan[k].y2, 0);  
            } else {  
                remove(scan[k].y1, scan[k].y2, 0);  
            }  
            if (k >= 1) {  
                perimeter += 2 * now_line * (scan[k].x - scan[k - 1].x);    //加上两条横边  
            }  
            perimeter += Math.abs(node[0].m - now_m);   //加上竖边  
            now_m = node[0].m;  
            now_line = node[0].line;  
        }  
        System.out.println("perimeter = " + perimeter); //expected:228  
    }  
      
      
    /** 
     * 初始化 
     * @param rectangleCount 矩形的个数 
     * 竖边（扫描线）的条数为rectangleCount * 2 
     * y轴坐标的坐标值也是rectangleCount * 2 
     */  
    public void init(int rectangleCount) {  
        int N = rectangleCount * 2;  
        int nodeCount = getNodeCount(N);  
        node = new Node[nodeCount];  
        for(int i = 0, len = node.length; i < len; i++) {  
            node[i] = new Node();  
        }  
        scan = new ScanLine[N];  
        for(int i = 0, len = scan.length; i < len; i++) {  
            scan[i] = new ScanLine();  
        }  
        y = new int[N];  
    }  
      
    /** 
     * 求得线段树的结点个数 
     * 线段树用数组存储，若表示的范围是[1,n]那么这个完全二叉树的高度为h=ceil(log2N) 
     * 结点数为：1 + 2 + 4 + 8 + ... + 2^h （根结点为第0层） 
     */  
    public int getNodeCount(int n) {  
        int result = 1;  
        int base = 1;  
        int height = (int) Math.ceil(Math.log(n) / Math.log(2));  
        for(int i = 1; i <= height; i++) {  
            base *= 2;  
            result += base;  
        }  
        return result;  
    }  
      
    //Set可去重，TreeSet可排序  
    private Set<Integer> sortAndMakeUnique(int[] y) {  
        Set<Integer> set = new TreeSet<Integer>();  
        for (int i : y) {  
            Integer j = Integer.valueOf(i);  
            set.add(j);  
        }  
        return set;  
    }  
      
    public void build(int left, int right, int i) {  
        node[i].left = left;  
        node[i].right = right;  
        node[i].lbd = 0;  
        node[i].rbd = 0;  
        node[i].count = 0;  
        node[i].line = 0;  
        node[i].m = 0;  
        if (right - left > 1) {  
            int mid = left + (right - left) / 2;  
            build(left, mid, 2 * i + 1);  
            build(mid, right, 2 * i + 2);  
        }  
    }  
  
    public void insert(int left, int right, int i) {  
        if (y[node[i].left] == left && y[node[i].right] == right) {  
            node[i].count++;  
        } else {  
            if (node[i].right - node[i].left == 1) {  
                return;  
            } else{  
                int mid = node[i].left + (node[i].right - node[i].left) / 2;  
                if (right <= y[mid]) {  
                    insert(left, right, 2 * i + 1);  
                } else if (left >= y[mid]){  
                    insert(left, right, 2 * i + 2);  
                } else {  
                    insert(left, y[mid], 2 * i + 1);  
                    insert(y[mid], right, 2 * i + 2);  
                }  
            }  
        }  
        update_m(i);  
        update_line(i);  
    }  
      
    public void remove(int left, int right, int i) {  
        if (y[node[i].left] == left && y[node[i].right] == right) {  
            node[i].count--;  
        } else {  
            if (node[i].right - node[i].left == 1) {  
                return;  
            } else{  
                int mid = node[i].left + (node[i].right - node[i].left) / 2;  
                if (right <= y[mid]) {  
                    remove(left, right, 2 * i + 1);  
                } else if (left >= y[mid]) {  
                    remove(left, right, 2 * i + 2);  
                } else {  
                    remove(left, y[mid], 2 * i + 1);  
                    remove(y[mid], right, 2 * i + 2);  
                }  
            }  
        }  
        update_m(i);  
        update_line(i);  
    }  
      
    public void update_m(int i) {  
        if (node[i].count > 0) {  
            node[i].m = y[node[i].right] - y[node[i].left];  
        } else {  
            if (node[i].right - node[i].left == 1) {  
                node[i].m = 0;  
            } else {  
                node[i].m = node[2 * i + 1].m + node[2 * i + 2].m;  
            }  
        }  
    }  
      
    public void update_line(int i) {  
        if (node[i].count > 0) {  
            node[i].lbd = 1;  
            node[i].rbd = 1;  
            node[i].line = 1;  
        } else {  
            if (node[i].right - node[i].left == 1) {  
                node[i].lbd = 0;  
                node[i].rbd = 0;  
                node[i].line = 0;  
            } else {  
                node[i].lbd = node[2 * i + 1].lbd;  
                node[i].rbd = node[2 * i + 2].lbd;  
                node[i].line = node[2 * i + 1].line + node[2 * i + 2].line;  
                if (node[2 * i + 1].rbd == 1 && node[2 * i + 2].lbd == 1) { 
                	//左右孩子结点刚好连续上了，则跨越的段数要减1  
                    node[i].line--;  
                }  
            }  
        }  
    }  
}
